from functools import cache


# 方法一：记忆化搜索
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:

        # 记忆化搜索
        n, m = len(text1), len(text2)

        # 转换为 选 还是 不选 问题
        @cache
        def dfs(i, j):

            if i < 0 or j < 0:
                return 0
            # 两个相等 选， 没有不选的情况，因为求公共子序列，越多越好（贪心）
            if text1[i] == text2[j]:
                # i-1，j-1 递归到下一个 +1：为公共子序列长度+1
                return dfs(i - 1, j - 1) + 1
            # 不相等，考虑 不相等时递归的所有情况，递归下去，取最值
            # 递归 i-1 and j-1 的max
            return max(dfs(i - 1, j), dfs(i, j - 1))

        return dfs(n - 1, m - 1)


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:

        n, m = len(text1), len(text2)

        # 递归转dp 一比一 翻译
        # i,j==>i+1,j+1 避免 i-1,j-1的时候出现负数下标
        f = [[0] * (m + 1) for _ in range(n + 1)]
        for i, x in enumerate(text1):
            for j, y in enumerate(text2):
                if x == y:

                    f[i + 1][j + 1] = f[i][j] + 1
                else:
                    f[i + 1][j + 1] = max(f[i][j + 1], f[i + 1][j])
        return f[n][m]

"""
进阶：如果要求返回最长的子序列呢？

根据得到的dp矩阵，逆序寻找路径
"""

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> str:
        n, m = len(text1), len(text2)
        # 递归转 dp 一比一 翻译
        # i,j==>i+1,j+1 避免 i-1,j-1 的时候出现负数下标
        f = [[0] * (m + 1) for _ in range(n + 1)]
        for i, x in enumerate(text1):
            for j, y in enumerate(text2):
                if x == y:
                    f[i + 1][j + 1] = f[i][j] + 1
                else:
                    f[i + 1][j + 1] = max(f[i][j + 1], f[i + 1][j])

        # 回溯找出最长公共子序列
        result = []
        i, j = n, m
        while i > 0 and j > 0:
            if text1[i - 1] == text2[j - 1]:
                result.append(text1[i - 1])
                # 向左上方移动，继续回溯
                i -= 1
                j -= 1
            # 如果上方位置的值大于左方位置的值
            elif f[i - 1][j] > f[i][j - 1]:
                # 向上移动，继续回溯(因为遍历的时候是取max，回溯也是取max)
                i -= 1
            else:
                # 否则向左移动，继续回溯
                j -= 1

        # 由于是逆序添加字符，需要反转结果列表并转换为字符串
        return ''.join(result[::-1])

